<html>
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />    
        <title>High Performance Primitive Collections (HPPC)</title>

        <link rel="stylesheet" type="text/css" href="resources/custom.css">
    </head>

    <body>
        High Performance Primitive Collections (HPPC) library provides
        typical data structures (lists, stacks, sets and maps) 
        that are generated for all Java primitive types 
        (<code>byte</code>, <code>int</code>, etc.) from a single template
        to conserve memory and boost performance.

        <p class="sectionTitle">Why HPPC?</p>

        <p>The Java Collections package is in many ways excellent, but it cannot
        be used for primitive types without autoboxing (which kills the 
        runtime performance due to increased memory use and garbage collector overhead).</p>

        <p>This library has slightly different design goals than Java Collections (and many other
        collection packages). For example, the internals of each class are open
        and subject to free hacking and tuning up to one's wishes.</p>


        <p class="sectionTitle">Why not other primitive collection libraries?</p>

        <p>There are a few projects implementing collections over primitive types:
            <a href="https://fastutil.dsi.unimi.it/">fastutil</a>,
            <a href="https://github.com/OpenHFT/Koloboke">Koloboke</a>,
            <a href="https://pcj.sourceforge.net/">PCJ (obsolete)</a>,
            <a href="https://trove4j.sourceforge.net/">GNU Trove (obsolete)</a>,
            <a href="https://commons.apache.org/primitives/">Apache Primitive Collections (obsolete)</a>.</p>

        <p>Historically, some of these libraries were released on commercially forbidding licenses
        (fastutil) and others appeared to be abandoned (PCJ), so HPPC was created to fill this
        gap. Since then things have changed quite a lot (fastutil is now Apache-licensed,
        Koloboke has been released), but HPPC still remains a small memory footprint and
        does the job. If you require full Java collections compliance, try
        <a href="https://fastutil.dsi.unimi.it/">fastutil</a>, or Koloboke, they are both
        very, very good.</p>


        <p class="sectionTitle">Assumptions and goals of HPPC</p>

        <p>We assume that:</p>
        <ul>
            <li>The programmer knows what he's doing and may wish to access internal
            storage of a given collection's class directly (not using predefined
            iterators, for example).</li>

            <li>Vast majority of scenarios use single-threaded access. There is little
            point in repeated verification for concurrent modifications, for example.</li>

            <li>The programs (algorithms) that use HPPC are unit-tested
            and regression-tested during development with assertions enabled, so their 
            behavior in production systems does not have to be restrictively verified 
            (we can assume the code should break during testing/ development when
            assertions are enabled).</li>
        </ul>

        <p>From these assumptions stem the following design drivers:</p>
        <ul>
            <li>Data types in the HPPC are as simple as possible and expose
            internal storage for any optimisations one may wish to do from within the 
            end-application code.</li>

            <li>Verification of parameter and state validity is done <b>optionally</b>
            using assertions. This means that contracts are only checked if requested at
            runtime (using Java 1.4+ <code>-ea</code> switch). When the algorithm is 
            tested and verified, it can run with no additional overhead from 
            contract checks.</li>

            <li>We tried to avoid complex interface hierarchies, although certain
            interfaces are defined for clarity. The programmer should still choose 
            a proper data structure at design-time and should know what he's doing.</li>

            <li>HPPC provides utilities for the most common tasks like filtering, iterating
            or joining collections, but these utilities are usually more expensive than implementing
            a low-level direct access to the data storage (which may be done if needed).</li>

            <li>There is no special support for data serialization.</li>

            <li>The implementation is not thread safe and does not attempt to provide 
            fast-failing concurrency problems detection.</li>
        </ul>


        <p class="sectionTitle">Design and implementation assumptions</p>
        
        <ul>
            <li>We want HPPC class templates to be implemented as <b>regular Java classes (with generics)</b> 
            so that typical programming tools can be used for development, testing, etc.</li>

            <li>We want HPPC class templates to be usable as generic-collection classes (for boxed
            numeric types or any other <code>Object</code> types), but at the same time we want
            specialized classes to be automatically-generated for primitive-types 
            (to limit memory consumption and boost performance due to JIT optimisations).</li>
        </ul>


        <p class="sectionTitle">Interfaces and their relation to Java Collections API</p>
        
        <p>HPPC is not strictly modeled after Java Collections API, although we did
        try to make the APIs look similar enough for comfortable use. 
        One particular thing largely missing in HPPC are "view" projections 
        (sublists or views over the collection of keys or values). Certain classes provide such views
        (like {@linkplain com.carrotsearch.hppc.ObjectObjectHashMap 
        <code>ObjectObjectHashMap</code>}), but for the most part, specific methods are
        provided that accept ranges or closure-like filters. If performance is still unsatisfactory,
        the internals of each class are available for direct manipulation.</p>

        <p>Rough relationships between Java Collections classes and HPPC classes are
        presented in the table below.</p>

        <table class="nice">
        <caption>Relationships between HPPC and Java Collections.</caption>
        <thead>
            <tr class="odd">
                <th class="empty"></th>
                <th scope="col">Java Collections</th>
                <th scope="col">HPPC (primitives)</th>  
                <th scope="col">HPPC (generics)</th>
            </tr>
        </thead>
        <tbody>
        <tr>
            <th scope="row" class="column1">bit sets</th>
            <td><code>java.util.BitSet</code></td>
            <td><code>BitSet</code></td>
            <td>n/a</td>
        </tr>

        <tr class="odd">
            <th scope="row" class="column1">array-backed lists</th>
            <td><code>java.util.ArrayList</code>, <code>java.util.Vector</code></td>
            <td><code><span class="red nobr">[type]</span>ArrayList</code></td>
            <td>{@linkplain com.carrotsearch.hppc.ObjectArrayList
                <code>ObjectArrayList&lt;<span class="red nobr">T</span>&gt;</code>}</td>
        </tr>
        
        <tr>
            <th scope="row" class="column1">stacks</th>
            <td><code>java.util.Stack</code></td>
            <td><code><span class="red nobr">[type]</span>Stack</code></td>
            <td>{@linkplain com.carrotsearch.hppc.ObjectStack 
                <code>ObjectStack&lt;<span class="red nobr">T</span>&gt;</code>}</td>
        </tr>

        <tr class="odd">
            <th scope="row" class="column1">deques</th>
            <td><code>java.util.ArrayDeque</code></td>
            <td><code><span class="red nobr">[type]</span>ArrayDeque</code></td>
            <td>{@linkplain com.carrotsearch.hppc.ObjectArrayDeque
                <code>ObjectArrayDeque&lt;<span class="red nobr">T</span>&gt;</code>}</td>
        </tr>

        <tr>
            <th scope="row" class="column1">hash sets</th>
            <td><code>java.util.HashSet</code></td>
            <td><code><span class="red nobr">[keyType]</span>HashSet</code></td>
            <td>
                {@linkplain com.carrotsearch.hppc.ObjectHashSet
                <code>ObjectHashSet&lt;<span class="red nobr">K</span>&gt;</code>}
                <div class="vsep"></div>
                <code><span class="red nobr">[keyType]</span>HashSet</code>
            </td>
        </tr>

        <tr>
            <th scope="row" class="column1">hash maps</th>
            <td><code>java.util.HashMap</code></td>
            <td><code><span class="red nobr">[keyType][valueType]</span>HashMap</code></td>
            <td>
                {@linkplain com.carrotsearch.hppc.ObjectObjectHashMap
                <code>ObjectObjectHashMap&lt;<span class="red nobr">K, V</span>&gt;</code>}
                <div class="vsep"></div>
                <code><span class="red nobr">[keyType]</span>ObjectHashMap&lt;<span class="red nobr">V</span>&gt;</code>
                <div class="vsep"></div>
                <code>Object<span class="red nobr">[valueType]</span>HashMap&lt;<span class="red nobr">K</span>&gt;</code>
            </td>
        </tr>
        </tbody>
        </table>

        <p>The method-level API of the corresponding types is also similar, but distinct
        differences exist (consult the JavaDoc of each class).</p>

        <p class="sectionTitle"><a id="interfaces">Interfaces and container inheritance</a></p>

        <p>HPPC's interfaces are modeled to encapsulate
        the common functionality enforced from <i>all</i> the classes that 
        implement a given interface. The interface hierarchy is loosely inspired by STL.</p>

        <p>An overview of interfaces and their relationship to data structures implemented
        in HPPC is depicted graphically below.</p>

        <p><img src="resources/interfaces.png" alt="HPPC interfaces"></p>
    </body>
</html>
